/**
 * 数组中有一个数字出现次数超过数组长度的一半,请找出这个数字.
 * 例如:输入一个长度为9 的数组{1,2,3,2,2,2,5,4,2}.由于数字 2在数组中出现了5次,超过数组长度的一半,
 * 因此输出2,如果不存在则输出0,
 */

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 思路1:定义map,使用<数字,次数>的映射关系,最后统计每个字符出现的次数
 * 思路2:排序,出现次数最多的数字,一定在数组的中间位置.然后检测中间出现的数字出现的次数是否符合要求
 * 思路3:目标条件:目标数据超过数组长度的一半,那么对数组,我们同时去掉两个不同的数字,到最后剩下的一个数就是该数字,
 *      如果剩下两个,那么这两个也是一样的,在其基础上把最后剩下的一个数字或者两个回到原来数组中,
 *      将数组遍历一遍统计一下数字出现次数进行最终判断
 *
 */
public class suanfa04 {

    //方法1
    public int MoreThanHalfNum_Solution1(int [] array) {
        if (array == null) {
            return 0;
        }
        Map<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < array.length; i++) {
            if (map.containsKey(array[i])) {
                int count = map.get(array[i]);
                count++;
                map.put(array[i],count);
            }else {
                map.put(array[i], 1);
            }
            if (map.get(array[i]) > array.length/2) {
                return array[i];
            }
        }
        return 0;
    }
    //方法2
    public int MoreThanHalfNum_Solution2(int [] array) {
        if (array == null) {
            return 0;
        }
        Arrays.sort(array);
        int target = array[array.length/2];
        int count = 0;
        for (int i = 0; i < array.length; i++) {
            if (target == array[i]) {
                count++;
            }
        }
        if (count > array.length/2) {
            return target;
        }
        return 0;
    }
    //方法3
    public int MoreThanHalfNum_Solution3(int[] array) {
        if (array == null) {
            return 0;
        }
        int target = array[0];
        int times = 1;
        for (int i = 1; i < array.length; i++) {
            if (times == 0) {
                target = array[i];
                times = 1;
            }else if (target == array[i]) {
                times++;
            }else {
                times--;
            }
        }
        times = 0;
        for (int i = 0; i < array.length; i++) {
            if (target == array[i]) {
                times++;
            }
        }
        return times > array.length / 2 ? target : 0;
    }
}
